package zuo.algo.c06;

import zuo.algo.data.LinkedNode;

/**
 * 00:02-两个链表相交问题
 */
public class FindFirstIntersectNode {

    public static LinkedNode findFirstIntersectNode(LinkedNode head1, LinkedNode head2) {
        LinkedNode node1 = getRingFirstNode(head1);
        LinkedNode node2 = getRingFirstNode(head2);
        if (node1 != null && node2 == null) {
            return null;
        }
        if (node1 == null && node2 != null) {
            return null;
        }
        if (node1 == null && node2 == null) {
            // 两个都无环
            return findNodeForNoRing(head1, head2);
        }
        if (node1 != null && node2 != null) {
            // 两个都有环
            if (node1 == node2) {
                // 入环节点相同
                return findNodeForSameRing(head1, head2, node1);
            }
            return node1;
        }
        return null;
    }

    public static LinkedNode findNodeForSameRing(LinkedNode head1, LinkedNode head2, LinkedNode first) {
        int len1 = 0, len2 = 0;
        LinkedNode node1 = head1, node2 = head2;
        while (node1 != first) {
            len1++;
            node1 = node1.next;
        }
        while (node2 != first) {
            len2++;
            node2 = node2.next;
        }
        node1 = len1 > len2 ? head1 : head2;
        node2 = len1 <= len2 ? head1 : head2;
        for (int i = 0; i < Math.abs(len1 - len2); i++) {
            node1 = node1.next;
        }
        while (node1 != null) {
            if (node1 == node2) {
                return node1;
            }
            node1 = node1.next;
            node2 = node2.next;
        }
        return null;
    }

    public static LinkedNode findNodeForNoRing(LinkedNode head1, LinkedNode head2) {
        LinkedNode end1 = head1, end2 = head2;
        int len1 = 0, len2 = 0;
        while (end1 != null && end1.next != null) {
            len1++;
            end1 = end1.next;
        }
        while (end2 != null && end2.next != null) {
            len2++;
            end2 = end2.next;
        }
        if (end1 != end2) {
            return null;
        }
        LinkedNode node1 = len1 > len2 ? head1 : head2;
        LinkedNode node2 = len1 <= len2 ? head1 : head2;
        for (int i = 0; i < Math.abs(len1 - len2); i++) {
            node1 = node1.next;
        }
        while (node1 != null) {
            if (node1 == node2) {
                return node1;
            }
            node1 = node1.next;
            node2 = node2.next;
        }
        return null;
    }

    public static LinkedNode getRingFirstNode(LinkedNode head) {
        LinkedNode fast = head, slow = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast != slow) {
            return null;
        }
        fast = head;
        while (fast != null) {
            if (fast == slow) {
                return fast;
            }
            fast = fast.next;
            slow = slow.next;
        }
        return null;
    }

    public static void main(String[] args) {
        LinkedNode head1 = new LinkedNode(1);
        head1.next = new LinkedNode(2);
        LinkedNode head2 = new LinkedNode(-1);
        LinkedNode node1 = new LinkedNode(3);
        LinkedNode node2 = new LinkedNode(4);
        head1.next.next = node1;
        head2.next = node1;
        node1.next = node2;
        node1 = findFirstIntersectNode(head1, head2);
        System.out.println(node1.val);

        node2.next = node1;
        node2 = findFirstIntersectNode(head1, head2);
        System.out.println(node2.val);
    }
}
